package com.Algorithm.DynamicProgramming.LCS问题;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2022/04/14/14:51
 * @Description:
 * @Target:
 */
public class 最长公共子序列_DP {
     // asdfghjkl
    // 6sasdfghgbtv

    public static void main(String[] args) {
/*        String ss1 = "v1casd2cadw3wefq4fqwe5fwqe6qf7fqwe8fqwe9";
        String ss2 = "ukik1kyi2yuik3kyu4loiul5myu6myuik7myu8myu9"; */
        String ss1 = "addbbccaacbddbbb";
        String ss2 = "ddcddcbcdbcbbbdabdcddabddcadbbbbdddabacaadcdcaacd";

        int[] ints1 = new int[ss1.length()];
        int[] ints2 = new int[ss2.length()];


        for (int i = 0; i < ss1.length(); i++) {
            ints1[i] = ss1.charAt(i);
        }

        for (int i = 0; i < ss2.length(); i++) {
            ints2[i] = ss2.charAt(i);
        }


        DP(ints1,ints2);
    }

    static void DP(int[] ints1,int[] ints2){
        int[][] ints = new int[ints1.length+1][ints2.length+1];

        for (int i = 0; i < ints1.length; i++) {
            for (int j = 0; j < ints2.length; j++) {
                if (ints1[i]==ints2[j]){
                    ints[i+1][j+1] = ints[i][j]+1;
                }else {
                    ints[i+1][j+1] = Math.max(ints[i+1][j],ints[i][j+1]);
                    // 必须得选最大，有多个子序列的比较
//                    ints[i+1][j+1] = ints[i+1][j];
                }
            }
        }

        outPrint(ints);

        System.out.println(ints[ints1.length][ints2.length]);


    }

    static int DP_DiGui(int[] ints1,int[] ints2,int[][] ints){
        return 1;
    }

    static void DP_V1(int[] ints1,int[] ints2){


        int[] intsC1 = new int[ints2.length+1];
        int[] intsC2 = new int[ints2.length+1];


        for (int i = 0; i < ints1.length; i++) {
            for (int j = 0; j < ints2.length; j++) {
                if (ints1[i]==ints2[j]){
                    intsC2[j+1] = intsC1[j]+1;
                }else {
                    intsC2[j+1] = Math.max(intsC1[j+1],intsC2[j]);
                }
            }

            // intsC2的东西给intsC1,intsC2清空
            for (int k = 0; k < intsC2.length; k++) {
                intsC1[k] = intsC2[k];
                intsC2[k] = 0;
            }
        }

        for (int k = 0; k < intsC2.length; k++) {
            System.out.print(intsC1[k]+" ");
        }

        System.out.println();
        System.out.println(intsC1[ints2.length]);

    }

    static void DP_V2(int[] ints1,int[] ints2){  // 有问题，当遇到重复元素时无法计算，问题是无法获取上一个数组的值！！
        int[] intsC3 = new int[ints2.length+1];
        for (int i = 0; i < ints1.length; i++) {
            for (int j = 0; j < ints2.length; j++) {
                System.out.print(intsC3[j]+" ");

                if (ints1[i]==ints2[j]){
                    intsC3[j+1] = intsC3[j]+1;
                }else {
                    intsC3[j+1] = Math.max(intsC3[j],intsC3[j+1]);
                }

            }

            System.out.println();

        }

        for (int k = 0; k < intsC3.length; k++) {
            System.out.print(intsC3[k]+" ");
        }

        System.out.println();

        System.out.println(intsC3[ints2.length]);


    }


    // 打印二维数组
    static void outPrint(int[][] ints){
        for (int i = 0; i < ints.length; i++) {
            for (int j = 0; j < ints[0].length; j++) {
                System.out.print(ints[i][j]+" ");
            }
            System.out.println();
        }
    }



}
